package airthmetic.exercise.trie;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

public class _212_单词搜索II {
    class Trie {
        class TrieNode {
            private boolean isEnd;
            private int R = 26;
            private TrieNode[] tns;
            private String word;

            public TrieNode() {
                tns = new TrieNode[R];
            }

            public boolean contains(char ch) {
                return tns[ch - 'a'] != null;
            }

            public void put(char ch, TrieNode node) {
                tns[ch - 'a'] = node;
            }

            public TrieNode get(char ch) {
                return tns[ch - 'a'];
            }

            public void setEnd() {
                isEnd = true;
            }

            public boolean isEnd() {
                return isEnd;
            }

            public String getWord() {
                return this.word;
            }

            public void setWord(String word) {
                this.word = word;
            }


        }

        TrieNode root;

        public Trie() {
            root = new TrieNode();
        }

        public void insert(String word) {
            if (word == null || word.length() == 0) {
                return;
            }
            char[] wordArr = word.toCharArray();
            TrieNode node = root;
            for (char w : wordArr) {
                if (!node.contains(w)) {
                    node.put(w, new TrieNode());
                }
                node = node.get(w);
            }
            node.setEnd();
            node.setWord(word);
        }

        public boolean search(String word) {
            if (word == null || word.length() == 0) {
                return false;
            }
            TrieNode node = searchPrefix(word);
            return node != null && node.isEnd();
        }

        public TrieNode searchPrefix(String word) {
            if (word == null || word.length() == 0) {
                return null;
            }
            char[] wordArr = word.toCharArray();
            TrieNode node = root;
            for (char w : wordArr) {
                if (!node.contains(w)) {
                    return null;
                }
                node = node.get(w);
            }

            return node;
        }

        public boolean startsWith(String prefix) {
            if (prefix == null || prefix.length() == 0) {
                return false;
            }
            TrieNode node = searchPrefix(prefix);
            return node != null;
        }
    }

    public int m;
    public int n;

    public List<String> findWords(char[][] board, String[] words) {
        // 拿到x和y
        m = board.length;
        n = board[0].length;
        HashSet<String> res = new HashSet();
        boolean[][] used = new boolean[m][n];
        Trie trie = new Trie();
        for (int k = 0; k < words.length; k++) {
            String w = words[k];
            trie.insert(w);

        }

        Trie.TrieNode trieNode = trie.root;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (trieNode.contains(board[i][j])) {
                    backtrack(i, j, board, used, trieNode, res);
                }
            }
        }

        return new ArrayList(res);
    }

    public int[][] fangxiang = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public void backtrack(int i, int j, char[][] board, boolean[][] used, Trie.TrieNode trieNode, HashSet<String> res) {
        // terminal
        if (!inBoard(i, j) || used[i][j]) {
            return;
        }

        if (!trieNode.contains(board[i][j])) {
            return;
        }
        used[i][j] = true;
        trieNode = trieNode.get(board[i][j]);
        if (trieNode.isEnd()) {
            res.add(trieNode.word);
        }



        // for (int x = 0; x < fangxiang.length; x++) {
        //     int newI = i + fangxiang[x][0];
        //     int newJ = j + fangxiang[x][1];
        //     backtrack(newI, newJ, board, used, trieNode, res);
        //     used[i][j] = false;
        // }

        backtrack(i+1,j,board,used,trieNode,res);
        backtrack(i,j+1,board,used,trieNode,res);
        backtrack(i-1,j,board,used,trieNode,res);
        backtrack(i,j-1,board,used,trieNode,res);
        used[i][j] = false;

    }

    public boolean inBoard(int i, int j) {
        return i >= 0 && i < m && j >= 0 && j < n;
    }

    public static void main(String[] args) {

//        char[][] board = new char[1][1];
//        board[0][0] = 'a';

        char[][] board = new char[2][2];
        board[0][0] = 'a';
        board[0][1] = 'b';
        board[1][0] = 'c';
        board[1][1] = 'd';

//        System.out.println(new _212_单词搜索II().findWords(board, new String[]{"a"}));
        System.out.println(new _212_单词搜索II().findWords(board, new String[]{"a", "b", "c", "d"}));
    }
}
